#
# @lc app=leetcode.cn id=669 lang=python
#
# [669] 修剪二叉搜索树
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def trimBST(self, root, low, high):
        """
        :type root: Optional[TreeNode]
        :type low: int
        :type high: int
        :rtype: Optional[TreeNode]
        """

        self.low = low
        self.high = high
        root = self.loop(root)
        return root


    def loop(self, node):
        if node is None:
            return

        if node.val < self.low:
            return self.loop(node.right)
        elif node.val > self.high:
            return self.loop(node.left)

        node.left = self.loop(node.left)
        node.right = self.loop(node.right)
        return node
        
# @lc code=end

